package algorithm.sort;

import algorithm.RandomArr;
import org.junit.Test;

import java.util.Arrays;

public class MergeSort4 {

  @Test
  public void test1() {
    this.arr = new int[]{1, 3, 5, 10, 2, 6, 9};
    merge(0, 3, this.arr.length - 1);
    System.out.println(Arrays.toString(this.arr));
  }

  @Test
  public void test2() {
    for (int i = 0; i < 100; i++) {

      this.arr = RandomArr.Arr(10);
      sort(0, this.arr.length - 1);
      System.out.println(Arrays.toString(this.arr));

      int pre = this.arr[0];
      for (int j = 0; j < this.arr.length; j++) {
        if (pre > this.arr[j]) {
          System.out.println("验证未通过");
          System.out.println(Arrays.toString(this.arr));
          break;
        } else {
          pre = this.arr[j];
        }
      }
    }

  }

  int[] arr = null;

  public void sort(int low, int hight) {

    if (low >= hight) {
      return;
    }
    int mid = (hight + low) / 2;
    sort(low, mid);
    sort(mid + 1, hight);

    merge(low, mid, hight);

  }

  //[low,mid] (mid,high]
  public void merge(int low, int mid, int high) {
    if (low >= high) {
      return;
    }
    int[] tmparr = new int[mid - low + 1];
    for (int i = low, j = 0; i <= mid; i++, j++) {
      tmparr[j] = this.arr[i];
    }

    int ai = 0;
    int bi = mid + 1;
    int cur = low;
    while (ai <= tmparr.length - 1 || bi <= high) {
      if (bi > high || (ai <= tmparr.length - 1 && tmparr[ai] < this.arr[bi])) {
        //
        this.arr[cur++] = tmparr[ai++];
      } else {
        this.arr[cur++] = this.arr[bi++];
      }

    }

  }

}
